package array_linklist

import (
	"container/list"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

// 从尾到头打印链表
// https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
type ReversePrint struct{}

// solutionUseArray 基于切片实现
func (q ReversePrint) solutionUseArray(head *ListNode) []int {
	if head == nil {
		return nil
	}
	arr := make([]int, 0, 10)
	for head != nil {
		arr = append(arr, head.Val)
		head = head.Next
	}
	n := len(arr) - 1

	for k := 0; k <= n/2; k++ {
		arr[k], arr[n-k] = arr[n-k], arr[k]
	}
	return arr
}

// solutionUseList 基于list容器实现。其他语言用栈更好点
func (q ReversePrint) solutionUseList(head *ListNode) []int {
	if head == nil {
		return nil
	}
	arr := make([]int, 0)
	l := list.New()
	for head != nil {
		l.PushBack(head.Val)
		head = head.Next
	}
	for k := l.Len(); k > 0; k-- {
		ele := l.Back()
		arr = append(arr, ele.Value.(int))
		l.Remove(ele)
	}
	return arr
}

// solutionReverseList 改变原链表的结构：反转。不需要额外空间
func (q ReversePrint) solutionReverseList(head *ListNode) []int {
	if head == nil {
		return nil
	}
	var prev *ListNode
	node := head
	count := 0
	for node != nil {
		next := node.Next
		node.Next = prev
		prev = node
		node = next
		count++
	}
	arr := make([]int, 0, count)
	for prev != nil {
		arr = append(arr, prev.Val)
		prev = prev.Next
	}
	return arr
}

// MaxSubArray 最大子序和
// https://leetcode-cn.com/problems/maximum-subarray/solution/
type MaxSubArray struct{}

func (m *MaxSubArray) dp01(nums []int) int {

	if nums == nil || len(nums) == 0 {
		return 0
	}
	// 1. 状态定义
	// dp[i] 表示前 i 个元素的最大连续子数组的和
	ans := 0
	dp := make([]int, len(nums))

	// 2. 状态初始化，数组中第一个元素的最大和就是第一个元素值
	dp[0] = nums[0]
	ans = nums[0]
	// 3. 状态转移
	// 转移方程：dp[i] = max(dp[i - 1], 0) + nums[i]
	for i := 1; i < len(nums); i++ {
		dp[i] = max(dp[i-1], 0) + nums[i]
		ans = max(ans, dp[i]) // 更新最大和
	}
	return ans
}
func (m *MaxSubArray) dp02(nums []int) int {
	if nums == nil || len(nums) == 0 {
		return 0
	}
	ans, prevSum := 0, 0

	for i := 1; i < len(nums); i++ {
		prevSum = max(prevSum, 0) + nums[i]
		ans = max(ans, prevSum)
	}
	return ans
}
func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}
